1. Field of the Invention
The present invention relates to a route searching system and method used for searching an optimal route in an on-vehicle type navigation system and the like. The present invention further relates to a navigation system including the route searching system, and relates to a computer program product for a route searching.
2. Description of the Related Art
In this kind of route searching system, for example, link costs of a route option, that is a route candidate, to a destination are calculated in a Dijkstra method, on the basis of road map data including at least nodes corresponding to intersections and at least a link corresponding to a road section between two nodes. More specifically, for example, a length of each road section consisting of the route option is converted to a link cost, and a total cost from a starting point or a current position to the destination is calculated for each route option. Finally or after repeating the calculation by certain times, one route option whose total cost is the lowest is searched as an optimal route.
Particularly, with regard to real roads, there are some tendencies, depending on traffic rules or regulations of individual countries. For example, it is often difficult to turn right at an intersection in Japan where drivers keep to the left side of the road. On the other hand, it is often difficult to turn left at an intersection in the United States of America where drivers keep to the right side of the road. In view of this, there is a technique in that a plurality of route options are searched by means of the aforementioned link cost calculation and one route option in which the number of the right turns is the lowest is determined as an optimal route (reference is made to Japanese Patent Application Laid-Open No. Hei 9-325038).
According to the aforementioned technique, however, under actual traffic conditions or road conditions, such a route option including certain right turns are eliminated from the route options presented by the navigation system, even in the case that it takes the shortest time to arrive at the destination only if the driving route contains certain right turns.
On the contrary, according to a technique in which a right turn and a left turn are not distinguished as seen in conventional route searching systems, or a technique in which a left turn simply takes a priority than a right turn (e.g. a technique in which a link cost of a road section that requires a right turn is set at a higher value than that of a road section that requires a left turn.), it is impossible to search an optimal route, taking account of actual traffic conditions that are varied depending on, for example, whether a right turn lane and/or a traffic signal with a right turn indicator exist(s) or not, even with regard to the same right turn. That is, in the technique in which a right turn and a left turn are not distinguished, a right turn may be indicated as a result of the route searching, at an intersection that may be very difficult to turn right under actual traffic conditions. Otherwise, similarly to the case disclosed by the aforementioned Japanese Patent Application Laid-Open No. Hei 9-325038, a right turn is not indicated but a “go straight” sign or a left turn may be indicated as a result of the route searching, even at an intersection that may be very easy to turn right under actual traffic conditions.